package cluster.old;

import org.apache.log4j.Logger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;

import org.grlea.log.SimpleLogger;

import cluster.Clusterable;
import cluster.Duster;

import color.Color;
import color.Hsv;

public class ClusterAlgorithm<E extends Clusterable> {
	/**
	 * Logger for this class
	 */
	private static final Logger logger = Logger
			.getLogger(ClusterAlgorithm.class);

	private static final SimpleLogger log = new SimpleLogger(ClusterAlgorithm.class);
	
	public ClusterAlgorithm(int size){
		//Duster.lookup = new DistLookup(size);
		Duster.nextID = 0;
	}
	@SuppressWarnings("unchecked")
	public ArrayList<Duster<E>> createDusters(ArrayList<E> list) {
		ArrayList<Duster<E>> n = new ArrayList<Duster<E>>(list.size());
		Iterator<E> i = list.iterator();
		while(i.hasNext()) n.add(new Duster<E>(i.next()));
		return n;
	}
	public Duster<E> pairCluster(ArrayList<Duster<E>> list) throws InstantiationException, IllegalAccessException{
		return pairCluster(list, 1).get(0);
	}
	public ArrayList<Duster<E>> pairCluster(ArrayList<Duster<E>> list, int size) throws InstantiationException, IllegalAccessException{		
		while(list.size() > size){
			int sIndex, cIndex, nIndex = 0;
			sIndex = (int)Math.floor(Math.random() * list.size());
			//sIndex = 0;
			//log.info("sIndex : " + sIndex + " size " + list.size());
			cIndex = getClosestIndex(sIndex, list);
			boolean mutual = false;
			log.debugObject("Clustering: length: ", list.size());
			while(!mutual){
				nIndex = getClosestIndex(cIndex, list);
				if(nIndex == sIndex){
					mutual = true;
				}
				else{
					sIndex = cIndex;
					cIndex = nIndex;
				}
				//log.debug("sIndex: " + sIndex + " cIndex " + cIndex + " nIndex " + nIndex);
			}
			ArrayList<Duster<E>> pair = new ArrayList<Duster<E>>();
			//log.info("sIndex: " + sIndex + " cIndex " + cIndex + " nIndex " + nIndex);
			pair.add(list.get(Math.max(sIndex, cIndex)));
			pair.add(list.get(Math.min(sIndex, cIndex)));
			list.set(Math.max(sIndex, cIndex), new Duster(pair));
			list.remove(Math.min(sIndex, cIndex));
			
		}
		return list;
	}
	
	public Duster<E> pairClosestCluster(ArrayList<Duster<E>> list) throws InstantiationException, IllegalAccessException{
		return pairClosestCluster(list, 1).get(0);
	}
	
	public ArrayList<Duster<E>> pairClosestCluster(ArrayList<Duster<E>> list, int size) throws InstantiationException, IllegalAccessException{		
		while(list.size() > size){
			log.debugObject("Clustering: length: ", list.size());
			mergePair(list);
		}
		return list;
	}
	public static int maxMutualTries = 1000;
	public Duster<E> groupCluster(ArrayList<Duster<E>> list, float mergeRatio) throws InstantiationException, IllegalAccessException{
		return groupCluster(list, mergeRatio, 1).get(0);
	}
	public ArrayList<Duster<E>> groupCluster(ArrayList<Duster<E>> list, float mergeRatio, int size) throws InstantiationException, IllegalAccessException{		
		
		while(list.size() > size){
			int sIndex, cIndex, nIndex = 0;
			sIndex = (int)Math.floor(Math.random() * list.size());
			//sIndex = 0;
			//log.info("sIndex : " + sIndex + " size " + list.size());
			cIndex = getClosestIndex(sIndex, list);
			boolean mutual = false;
			log.debugObject("Clustering: length: ", list.size());
			int tryCount = 0;
			while(!mutual){
				nIndex = getClosestIndex(cIndex, list);
				if(nIndex == sIndex){
					mutual = true;
				}
				else{
					sIndex = cIndex;
					cIndex = nIndex;
					tryCount++;
				}
				if(tryCount > list.size() * list.size()){
					mutual = true;
				}
				if(list.size() < 10)
					log.debug("sIndex: " + sIndex + " cIndex " + cIndex + " nIndex " + nIndex);
			}
			ArrayList<Integer> close = getWithinRange(sIndex, cIndex, mergeRatio, list);
			ArrayList<Duster<E>> children = new ArrayList<Duster<E>>();
			
			children.add(list.get(Math.max(sIndex, cIndex)));
			children.add(list.get(Math.min(sIndex, cIndex)));
			Iterator<Integer> i = close.iterator();
			while(i.hasNext()) children.add(list.get(i.next().intValue()));
			list.set(Math.max(sIndex, cIndex), new Duster<E>(children));
			close.add(new Integer(Math.min(sIndex, cIndex)));
			Collections.sort(close);
			ListIterator<Integer> li = close.listIterator(close.size());
			while(li.hasPrevious()) list.remove(li.previous().intValue());
			
		}
		return list;
	}
	
	public void mergeDusters(Duster<E> root, float mergeDist){
		if(root.isLeaf()) return;
		if(root.maxDev < mergeDist) 
			root.convertToLeaf();
		else{
			Iterator<Duster<E>> i = root.children.iterator();
			while(i.hasNext()) mergeDusters(i.next(), mergeDist);
		}	
	}
	
	public void collapseDusters(Duster<E> root, float devDiv){
		if(root.isLeaf()) return;
		float maxDev = root.maxDev / devDiv;
		boolean allBelow = false;
		while(!allBelow){
			allBelow = true;
			Iterator<Duster<E>> i = root.children.iterator();
			ArrayList<Duster<E>> nu = new ArrayList<Duster<E>>();
			while(i.hasNext()){
				Duster<E> next = i.next();
				if(next.maxDev > maxDev){
					nu.add(next);
					allBelow = false;
				}   	
			}
			Iterator<Duster<E>> k = nu.iterator();
			while(k.hasNext()) root.assimilateChild(k.next());
		}
		Iterator<Duster<E>> i = root.children.iterator();
		while(i.hasNext()) collapseDusters(i.next(), devDiv);
	}
	
	public void setNumDusters(int num, Duster<E> root) throws InstantiationException, IllegalAccessException{
		if(root.isLeaf()) return;
		if(root.children.size() == num) return;
		while(root.children.size() != num){
			if(root.children.size() < num){
				float maxDist = 0;
				Duster<E> furthest = null;
				Iterator<Duster<E>> i = root.children.iterator();
				while(i.hasNext()){
					Duster<E> next = i.next();
					if(next.maxDev > maxDist && !next.isLeaf()){
						if(next.children.size() == 1)
							next.assimilateChildren();
						maxDist = next.maxDev;
						furthest = next;
					}
				}
				if(furthest == null) {
					if (logger.isDebugEnabled()) {
						logger
								.debug("setNumDusters(int, Duster<E>) - furthest="
										+ furthest);
					}

					return;
				}
				Duster<E> blackSheep = furthest.getBlackSheep();

				if (logger.isDebugEnabled()) {
					logger.debug("setNumDusters(int, Duster<E>) - blackSheep="
							+ blackSheep + furthest.children.size());
				}

				furthest.children.remove(blackSheep);
				root.addChild(blackSheep);
			}
			else if(root.children.size() < num){
				root.mergeChildren(root.getClosestChildren());
			}
		}
	}
	

	
	//@SuppressWarnings("unchecked")
/*
	
	private void initSearchArrays(ArrayList<Duster<ColorObservation>> colors){
		ArrayList<Duster<ColorObservation>> rSorted = new ArrayList<Duster<ColorObservation>>(colors);
		Collections.sort(rSorted, (Comparator<Color>) new Color.RedComparator());
		ArrayList<Duster<ColorObservation>> gSorted = new ArrayList<Duster<ColorObservation>>(colors);
		Collections.sort(gSorted, new Color.GrnComparator());
		ArrayList<Duster<ColorObservation>> bSorted = new ArrayList<Duster<ColorObservation>>(colors);
		Collections.sort(bSorted, new Color.BluComparator());
	}
	
	public Duster<ColorObservation> getClosest(int to, int dist){
		
		
		
		return null;
	}
	
	
	
	
	*/
	
	public static ArrayList<Color> generateRandomColors(int num){
		ArrayList<Color> list = new ArrayList<Color>();
		for(int i = 0; i < num; i++){
			Color c = new Color(new Hsv((float) (Math.random() * 2f*Math.PI - Math.PI), 
					   (float) Math.random(), (float) Math.random()));
			list.add(c);
			System.out.println("AddedClr: " + c.toString());
		}
		return list;
		
	}
	
	
	
	
	@SuppressWarnings("unchecked")
	public int getClosestIndex(int index, ArrayList<Duster<E>> l){
		//Iterator<Duster<? extends Clusterable>> i = l.iterator();
		float minDist = Float.MAX_VALUE;
		//int count = 0;
		int closest = -1;
		Duster<E> c = l.get(index);
		for(int i = l.size()-1; i >= 0; i--){
			if(i != index){
				float dist = c.getDistanceTo(l.get(i));
				if(dist < minDist){
					closest = i;
					minDist = dist;
				}
			}
		}
		//log.info("closest Index to " + index + " is " + closest + " minDist " + minDist);
		if(closest == -1)
			log.warn("no Closest found" + index + " size " + l.size());
		return closest;
	}
	
	public void mergePair(ArrayList<Duster<E>> l) throws InstantiationException, IllegalAccessException{
		Iterator<Duster<E>> i1 = l.iterator();
		Iterator<Duster<E>> i2;
		Duster<E> cd1 = null, cd2 = null;
		float closest = Float.MAX_VALUE;
		while(i1.hasNext()){
			Duster<E> d1 = i1.next();
			i2 = l.iterator();
			while(i2.hasNext()){
				Duster<E> d2 = i2.next();
				float dist = d1.getDistanceTo(d2);
				if(dist < closest){
					closest = dist;
					cd1 = d1;
					cd2 = d2;
				}
			}
		}
		l.remove(cd1);
		l.remove(cd2);
		ArrayList<Duster<E>> c = new ArrayList<Duster<E>>();
		c.add(cd1);
		c.add(cd2);
		Duster<E> d = new Duster<E>(c);
		if(closest < 0.5) d.convertToLeaf();
		l.add(new Duster<E>(c));
		
	}
	
	public ArrayList<Integer> getWithinRange(int index1, int index2, float mergeRatio, ArrayList<Duster<E>> l){
		//int count = 0;
		
		ArrayList<Integer> close = new ArrayList<Integer>();
		float shortest = Float.MAX_VALUE;
		Duster<E> c1 = l.get(index1);
		Duster<E> c2 = l.get(index2);
		float maxDist = c1.getDistanceTo(c2) * mergeRatio * 2;
		for(int i = l.size()-1; i >= 0; i--){
			if(i != index1 && i != index2){
				float dist = c1.getDistanceTo(l.get(i)) + c1.getDistanceTo(l.get(i));
				if(dist < maxDist) {
					if(dist < shortest) close.add(0, new Integer(i));
					else close.add(new Integer(i));
				}
			}
		}
		return close;
	}
	
	

	
	
}
